perm filename TEXT2[F8,ALS]1 blob
sn#319427 filedate 1977-12-05 generic text, type C, neo UTF8
COMMENT ā VALID 00014 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002
C00004 00003 Checkers on the Video-Brain
C00006 00004 If you type Y, the checker board is shown with the
C00009 00005 Having selected a piece that can move, you again move
C00012 00006 The basic rules of the game.
C00015 00007 HOW the CHECKERS program plays Checkers
C00018 00008 Most people find it hard to believe these numbers
C00021 00009 This process is repeated at each level of look-ahead,
C00024 00010 Having explored the complete game tree the program
C00027 00011 A brief history of computer games
C00030 00012 But why, one might ask, would anyone want to take the
C00033 00013 This was in 1833, remember, and the entire machine had
C00037 00014 Biographical Sketch
C00040 ENDMK
Cā;
Checkers
on the
Video-Brain
Checkers on the Video-Brain
HOW TO PLAY
To play Checkers against the Video-Brain, Insert the
Checkers cartridge, plug one JOY STICK cord into
socket 1 and push the start button.
The Video-Brain will respond by displaying the word
CHECKERS for a moment and then it will display the
following,
CHOOSE KEY
TOM T
DICK D
HARRY H
and wait for you to type the letter T or D or H.
These refer to the skill level desired, Robot Tom is
the least skilled and should be selected until you
have had an opportunity to assess your relative skill
as compared with the Video-Brain. Robot HARRY is the
best player of the three.
If any other key (including the space bar) is struck,
the Video-Brain will accept this as equivalent to the
letter T. This is done so that a young child can be
told to reply to all questions with the space bar.
The Video-Brain will next display,
YOU MOVE FIRST? Y OR N
and then wait for you to type a Y or an N. As before,
any key other than the N key will be accepted as a Y
(children usually like to play first).
1
If you type Y, the checker board is shown with the
Black pieces (for you) at the bottom, the message
YOUR MOVE
is displayed, a small square spot (called the cursor)
will appear somewhere on the board and the Video-Brain
will wait for your first move. You may have to move
the Joy Stick lever back and forth and up and down a
few times before you will be able to see the cursor.
If you type N, the Video-Brain will play BLACK and it
will play first. Your (RED) pieces will appear at the
bottom of the screen. Note that your pieces are
always those that initially appear at the bottom of
the screen and that your non-king pieces can only move
in the upward direction.
It is easy to learn to play checkers with the
Video-Brain, even if you do not know the game. The
Video-Brain will not let you make illegal moves, and
it will usually tell you what you are doing wrong.
The basic rules are listed on page 4 of this booklet.
Moves are made by using the JOY STICK to move the
cursor until it is brought to rest on a piece that you
wish to move. You may have to practice before you
will be able to do this easily.
When you have the cursor properly centered on the
piece you want to move, you push the HIT button on the
side of the JOY STICK case. If the selected piece can
move, a corner will begin to blink. If the selected
piece cannot move, a message will inform you of this
fact and you must selest a different piece.
2
Having selected a piece that can move, you again move
the JOY STICK and select the square to which the piece
is to move. With the cursor on this desired square
you again press the HIT BUTTON. If the attempted move
is a legal move, the piece will be moved and the
Video-Brain will begin to plan its move and it will
display the message
MY MOVE.
If you try to make an illegal move the Video-brain
will tell you why it is illegal and wait for you to
make a legal move. After several illegal attempts the
Video-Brain will cancel the piece selection and you
must then reselect the piece that you want to move.
Occasionally you may have a double jump (see
explanation below). To make a double jump you make
the first jump just as discribed above. The
video-Brain will then prompt you by displaying
CONTINUE JUMP
and you then move the cursor to the final position or
if perchance you have a triple jump then to the next
"touch" point where the process is repeated.
That's all there is to it. If you are a good enough
player to get the best of the Video-Brain, it will
anticipate its own defeat and tell you how many moves
it should take you to win. Conversely if it expects
to win, you are also told.
3
The basic rules of the game.
Checkers is a two person game played on a checker
board in which the two players take turns in moving
one of their pieces.
The object of the game is to have the last move, which
is usually done by capturing all of your opponent's
pieces.
Pieces are of two kinds, MEN and KINGS. Your MEN can
only move upward on the screen while the Video-brain's
MEN can only move downward. MEN, when they reach the
last row are promoted and become KINGS and can then
move backward as well as forward.
Pieces move along diagonals, a single square at a time
except when "jumping" an opponent's piece. Opponent's
pieces are captured by jumping them.
A jump move must be made whenever such a move is
available. To jump, you must have one of your pieces
in position next to an opponent's piece with an empty
square just beyond the opponent's piece, all of this
along a diagonal in a legal direction. You then move
your piece to this empty square and the Video-Brain
removes the captured piece.
Occasionally, it is possible (and also compulsory) to
jump more than one piece when the jumping piece lands
on a square which puts it into a position to make
still another jump. There is one exception to this
rule: a piece that is promoted on reaching the last
row cannot continue to jump until after an intervening
opponents move.
4
HOW the CHECKERS program plays Checkers
The checkers program plays checkers very much the way
that you play the game, that is it attempts to trace
out the consequences of its proposed moves with due
allowance for how you will respond to its move and
considering how it will than be able to respond and
what you might do next, etc. for several moves in
advance of the current position. That is, the program
"looks ahead".
People sometimes think that one could simply store all
of the possible board situations with the desired
replies, but this is quite impossible on even the
largest computer that could ever be built.
So the program looks ahead. But it can look ahead for
only a very few moves,. Again, people quite fail to
realize how many different board positions would be
involved if one tried to look ahead very far. A
simple calculation will show what the problem is.
If we ignore jump moves to make the calculation easy
we can quickly get a feeling for the difficulty.
Normally, there are about 8 possible moves, so looking
ahead 2 moves involves considering 1 plus 8 plus 64 or
73 boards. Four moves ahead involves this number of
boards plus 512 plus 4096 or 4618 boards. But now the
numbers rapidly get out of hand because 8 moves ahead
calls for over 18 million boards and 16 moves calls
for over 300 million million boards! These numbers
are correct if one counts only the non-jump moves,
but, of courses, jump moves will actually occur and
more total moves will actually be played before these
astronomical numbers are reached. Normal games
usually take many more than 16 non-jump moves.
5
Most people find it hard to believe these numbers
because they do not fully appreciate what is known in
conmputer parlance as "the combinatorial explosion"
and because they instinctively feel that there could
not possiblly be this many different board positions.
Actually there are not this many different board
positions, many positions reached along one line of
play will be the same positions encountered along some
other line, but the point is that they have to be
looked at again before this fact becomes known, and we
are concerned with the number of times the boards must
be examined. The "combinatorial explosion" is real
and it is encountered in many different computer
programs and much of the art of computer programming
consists of clever ways of dealing with it.
So the program can only look ahead a very few moves
and certainly not far enough to see to the end of the
game.
Having looked ahead a few moves, the program then
tries to evaluate the resulting position. If some
pieces have been captured by one side, then the
sequence of moves which lead to this capture is
desirable for this side but, of course, not for the
other side. Sometimes there are no captures and then
the evaluation consists in assessing the relative
strength of the position: for example, whether one
side or the other controls the center of the board.
Now after the final board has been evaluated, the
program must back up giving each side (remember this
is all looking ahead and does not yet involve any
actual moves) the chance to replace the first chosen
move by alternate choices, and again following this
out to the practical limit in look ahead distance.
6
This process is repeated at each level of look-ahead,
all the way back to the initial move.
If all of the moves that are considered in this way
are shown on a piece of paper the resulting picture
looks very much like a tree, so this process is called
"backing up the tree". Maybe it should be called
"backing down the tree" but for some strange reason
the move trees are usually drawn up-side-down.
This backing up is done using a technique known in
computer jargon as the "alpha-beta heuristic". Don't
let this jargon disturb you because you already know
this technique intuitively. It simply means that you
cease to consider all the remaining possible moves
that your opponent might make in response to a move
that you are thinking aboue as soon as you have found
that he has one reply that is greatly to your
disadvantage. You further assume that your opponent
will do the same from his or her point of view. While
you can do this without any great trouble it becomes
quite complicated to express this intuitive concept as
a program for a computer which, of course, has no
intuition.
The use of the "alpha-beta heuristic" results in a
great saving in the number of moves that have to be
considers because it results in "tree pruning".
Without tree pruning, a computer would play very poor
checkers indeed or else it would take centuries to
make a single move. People who are good at games are
people who are good at "tree pruning".
7
Having explored the complete game tree the program
then selects what appears to be its best move and then
waits for you to make your move.
So a computer plays checkers very much as you do. The
only difference is that it must be given a very
detailed list of instructions, called a computer
program. These instructions are really commands
because they allow the computer no latitude at all in
its action. It is told exactly what to do by the
person who has prepared the program, but remember, it
is not told what move to make but it is told how to
"look-ahead", how to "evaluate", how to "back up the
tree", and how to "alpha-beta prune".
The proficiency that the computer appears to possess
is a mechanical reflection of the proficiency of the
person who wrote the program, subject, of course, to
the constraints imposed by the size of the computer.
The checkers program on the Video-brain cannot be
expected to play as well as it does on a million
dollar computer. You may be surprised to find how
well it does play, so try it.
8
A brief history of computer games
There have been many attempts throughout history to
construct machines that could play games. Most of the
very early attempts were either extremely crude or
they were out-and-out frauds.
There was, for example, the very famous chess-playing
machine constructed in 1769 by the Baron Kempelen.
This was taken on tour all over the world, and
deceived thousands of people into thinking that it
played the game automatically, when in fact a small
man was concealed inside. Edger Allen Poe described
this machine in detail. The device was said to have
defeated Napoleon who was considered to be a very good
player.
A chess playing machine, this time a real one, was
constructed by Signor Torres Quededo in about 1890
which played a chess end game and which with a rook
and a king could checkmate an opponent with a single
king.
As illustrated by these two examples, chess has been
the principle game that has attracted the designers of
game playing machines almost from beginning, although
there has been a great deal of work on other games,
and particularly on games such as Nim for which there
exist complete mathimatical solutions and on games
such as Tic Tac Toe that are simple enough to solve by
considering all possible plays to the end of the game.
With the advent of the modern digital computer, effort
has turned toward programming the computer to play the
games and attempts to build special machines for this
purpose has languished.
9
But why, one might ask, would anyone want to take the
time and incur the expense that is involved in getting
a computer to play a game. As computers are applied
to practical problems of greater and greater
complexity, one frquently finds that the complexity of
detail rather obscures the fundamental nature of the
problem and one becoming completely engulfed in
detail.
Games and particularly those games that have been
around for centuries seem to interest people because,
in a way they require the same kinds of thinking that
one must do in solving the problems of every day life.
But games do not have the immensity of detail that
real life problems have. The rules of a game are
fixed while those in real life are always subject to
different interpretations. Finally the criteria for
success are simple, one knows when one has won. So
games allow us to explore new techniques in the use of
computers under fixed conditions. Programming
computers to play games is them not simply playing
games and it is justified in terms of the new
techniques that are developed.
So programming a computer to play a game can have a
serious purpose. And besides it is fun.
But this is not an entirely modern idea. As early as
1833, a British mathematician, Charles Babbage, had
conceived the idea of his Analytical Engine and he
thought that he would be able to have his Analytical
Engine play chess. Babbage was a man ahead of his
time and he was to spend the rest of his life in an
unsuccessful attempt to build his Analytical Engine.
10
This was in 1833, remember, and the entire machine had
to be built out of gears and levers. The existing
technology was simply not up to the task and indeed
even today we would find it impractical to try to
build a computer with such parts.
Interestingly enough, Babbage planned to use all or
substantially all of the mathematical ideas that are
embodied in the present day computer. But the
computer had to wait until the present era when the
electronics art and our general industrial progress
made its development both possible and economically
desirable.
When the first large digital computers were still on
the drafting board, a number of different people took
up Babbage's old idea and began to think about how one
would program these computers to play games. Two of
these people were the British mathematicians Alan
Turing and Christofer Strachey, another was the
American mathematician Claud Shannon. These men
worked on chess.
The writer thought that chess was being over worked
and so he turned to the game of checkers. This was in
1947, and he has continued to work on a succession of
different programs to play checkers and he has been
using these programs as tools to investigate new
computer techniques off and on ever since that time.
If you are interested in this aspect of the problem,
you might like to read two papers, Some Studies in
Machine Learning Using the Game of Checkers" which
were published in the IBM Journal of Research and
Development, the first in Vol. 3 No. 3, July 1959 pp
211-229 and the second in Vol.11 No 6, November 1967
pp 601-617.
11
Biographical Sketch
Dr. Arthur L. Samuel, Adjunct Professor Emeritus at
Stanford University, has been involved in the
development and use of computers for a very long time,
start out in 1923 when he was a student at MIT and
worked on the Bush Differential Analyser (an analog
machine not a digital one).
After teaching at MIT for two years Dr. Samuel joined
the Bell Telephone Laboratories where he worked
largely on microwave tubes of the type used in Radar.
Leaving the Bell Laboratories in 1946, Dr. Samuel went
to the University of Illinois where he renewed his
interest in computers, this time in digital computers.
Computers became his dominant interest so he went with
IBM in 1949 and stayed with IBM until he reached their
compulsory retirement age. He was involved with just
about every phase in the research and development of
digital computers.
Since 1966 he has been in the Computer Science
Department at Stanford University and altho he was
made Emeritus in 1975 he continues to work full time.
He does take time out to do extensive traveling and to
undertake such side jobs as programing the Video-Brain
to play checkers.
Dr. Samuel has over 50 U.S. patents and has published
many technical papers. He was made a Fellow of the
American Physical Society, of the Institute of Radio
Engineers and of the American Institute of Electrical
Engineering and has received numerious other
professional honors.
12